#include "stdafx.h"
#include "stdlib.h"
#include "time.h"

struct Element
{
Element* next;
int value;
};
struct LinkedList
{
Element* head;
int length;
};

LinkedList* create_list()
{
	LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
	list->head=NULL;
	list->length=0;
	return list;
}
Element* create_elem(int value)
{
	Element* elem = (Element*)malloc(sizeof(Element));
	elem->next=NULL;
	elem->value=value;
	return elem;
}
void append_to_begin(LinkedList* list, Element* elem)
{
	elem->next=list->head;
	list->head=elem;
	list->length++;
}
void append_to_end(LinkedList* list, Element* elem)
{
	Element* el = list->head;
	if(el==NULL)
	{list->head=elem;}
	else
	{while(el->next)
	el=el->next;
	elem->next=NULL;
	el->next=elem;}
	list->length++;
}
int get_size(LinkedList* list)
{
	return list->length;
}
struct Element* find_el(LinkedList* list, int pos)
{
	if(pos>(list->length))
	{
		printf("\nelement not found\n");
		return 0;
	}
	else
	{	
		struct Element* el=list->head;
		for(int i=1;i<pos;i++)
		{
			el=el->next;
		}
		return el;
	}
}
void insert_after(LinkedList* list, int pos, Element* elem)
{
	Element* el = list->head;
	for(int i=1;i<pos;i++)
		el=el->next;
	elem->next=el->next;
	el->next=elem;
	list->length++;
}
void clear_el(LinkedList* list, Element* elem)
{
	struct Element* el = list->head;
	struct Element* prev = NULL;
	for(int i=1;i<=(list->length);i++)
	{
		if(elem==el)
		{	if(prev==NULL)
				list->head=el->next;
			else
				prev->next=prev->next->next;
			free(elem);
			list->length--;
			break;
		}
		prev=el;
		el=el->next;
	}
}
void clear_elem(LinkedList* list, int pos)
{
	Element* el = find_el(list,pos);
	clear_el(list,el);
}
void clear_list(LinkedList* list)
{
	Element* temp=NULL;
	Element* el = list->head;
	for(int i=1;i<=list->length;i++)
	{
		temp=el->next;
		free(el);
		el=temp;
	}
	free(list);
}
void print_list(LinkedList* list)
{
	Element* el = list->head;
	for(int i=1;i<(list->length);i++)
	{
		printf("%d ",el->value);
		el=el->next;
	}
	printf("%d\n",el->value);
}
int* convert_to_array(LinkedList* list)
{
	int* arr = (int*)malloc(sizeof(int)*(list->length));
	struct Element* el=list->head;
	for(int i=0;i<(list->length);i++)
	{
		arr[i]=el->value;
		el=el->next;
	}
	return arr;
}
struct Element* find_max(LinkedList* list)
{
	struct Element* el=list->head;
	struct Element* maxel=list->head;
	int max=maxel->value;
	for(int i=1;i<=(list->length);i++)
	{
		if(max<(el->value))
		{
			maxel=el;
			max=el->value;
		}
		el=el->next;
	}
	return maxel;
}
struct Element* find_min(LinkedList* list)
{
	struct Element* el=list->head;
	struct Element* maxel=list->head;
	int max=maxel->value;
	for(int i=1;i<=(list->length);i++)
	{
		if(max>(el->value))
		{
			maxel=el;
			max=el->value;
		}
		el=el->next;
	}
	return maxel;
}
void swap(LinkedList* list,Element* a,Element* b)
{
	Element* temp;
	if(a->next==NULL)
	{temp=a;a=b;b=temp;}

	Element* preva=list->head;
	if(preva==a)
		preva=NULL;
	else
	while(preva->next!=a)
		preva=preva->next;

	Element* posta=a->next;

	Element* prevb=list->head;
	while(prevb->next!=b)
		prevb=prevb->next;

	Element* postb=b->next;

	if(a->next==b)
	{
		if(preva==NULL)
		list->head=b;
		else
		preva->next=b;

		b->next=a;
		a->next=postb;
	}
	else
	{
		if(preva==NULL)
		{b->next=posta;
		list->head=b;}
		else
		{preva->next=b;
		b->next=posta;}

		prevb->next=a;
		a->next=postb;
	}
}
void sorting(LinkedList* list)
{
	Element* curr=list->head;
	Element* place=list->head;
	Element* min=list->head;
	for(int j=0;j<(list->length-1);j++)
	{
		for(int i=j+1;i<(list->length+1);i++)
		{
			if((curr->value)<(min->value))
				min=curr;
			curr=curr->next;
		}
		swap(list,place,min);
		place=min->next;
		curr=min->next;
		min=min->next;
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	struct LinkedList* klen=create_list();
	srand(time(NULL));
	for(int i=1;i<=10;i++)
	{
		struct Element* cherv=create_elem(rand()%100);
		append_to_begin(klen, cherv);
	}
	print_list(klen);
	sorting(klen);
	print_list(klen);
	return 0;
}

